package A一周刷爆LeetCode.A基础班.F二叉树;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * @author wei.zhao
 * @description: 求二叉树的最大深度
 * @date 2022年02月18日 9:48
 */
public class Code05_MaxDeepth {

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);
        head.left.left.left = new Node(8);
        int maxDeepth = getMaxDeepth(head);
        System.out.println("当前二叉树的最大深度是：" + maxDeepth);
    }

    public static int getMaxDeepth(Node head) {
        int result = 0;
        if (null == head) {
            return result;
        }
        LinkedList<Node> list = new LinkedList<>();
        // 记录每个节点所在的层级
        HashMap<Node, Integer> levelMap = new HashMap<>();
        list.add(head);
        levelMap.put(head, 1);
        result = 1;
        while (!list.isEmpty()) {
            Node pop = list.pop();
            Integer level = levelMap.get(pop);
            if (null != pop.left) {
                list.add(pop.left);
                levelMap.put(pop.left, level + 1);
                result=level+1;
            }
            if (null != pop.right) {
                list.add(pop.right);
                levelMap.put(pop.right, level + 1);
                result=level+1;
            }
        }
        return result;
    }

}
